#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

void Swap(int* arr, int left, int right)
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

void BackTrack(int* arr, int n, int start, int* pi, int** RetArrCol, int** RetArr)
{
    if (start == n)
    {
        RetArr[*pi] = (int*)malloc(sizeof(int) * n);
        memcpy(RetArr[*pi], arr, sizeof(int) * n);
        (*RetArrCol)[*pi] = n;
        *pi = *pi + 1;
    }
    else
    {
        for (int i = start; i < n; i++)
        {
            Swap(arr, i, start);
            BackTrack(arr, n, start + 1, pi, RetArrCol, RetArr);
            Swap(arr, i, start);
        }
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    int** RetArr = (int**)malloc(sizeof(int*) * 721);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 721);
    *returnSize = 0;
    BackTrack(nums, numsSize, 0, returnSize, returnColumnSizes, RetArr);
    return RetArr;
}

int main()
{

    return 0;
}